#ifndef GRAPHE_H
#define GRAPHE_H

#include "noeud.h"
#include "arete.h"



struct Graphe
{
	Noeud* noeuds;			/* Tableau des sommets du graphe */
	int nbN;

	Arete* poids;			/* Tableau des arêtes du graphe */
	int nbP;

	Noeud** importants; 	/* Tableau des adresses des sommets importants */
	int nbI;
};

typedef struct Graphe Graphe;


/* FONCTIONS D'INITIALISATION ET DE SUPPRESSION */

/* Crée un Graphe vide ayant nbNoeuds sommets */
Graphe nouveauGraphe(const int nbNoeuds);

/* Libère g (qui ne doit plus être utilisé ensuite) */
void testamentGraphe(Graphe* g);

/* Crée un Graphe dont les paramètres sont donnés par un fichier
   accessible par le chemin nomFichier, de type 1 (cf README) */
Graphe nouveauGrapheFichier1(const char* nomFichier);

/* Crée un Graphe dont les paramètres sont donnés par un fichier
   accessible par le chemin nomFichier, de type 2 (cf README) */
Graphe nouveauGrapheFichier2(const char* nomFichier);



/* ACCESSEURS ET MUTATEURS */

/* Retourne le nombre de Noeuds de g */
int getNbNGraphe(const Graphe* g);

/* Retourne le nombre d'Aretes de g*/
int getNbPGraphe(const Graphe* g);

/* Retourne le nombre de Noeuds importants de g */
int getNbIGraphe(const Graphe* g);

/* Retourne l'indice dans g du i-ème Noeud important
   (0<=i<g.nbI) */
int getIndiceImportant(const Graphe* g, const int i);

/* Retourne le i-ème Noeud de g (0<=i<g.nbN) */
Noeud getINoeud(const Graphe* g, int i);

/* Retourne l'Arete de g qui relie les sommets d'indices n1 et n2
   (0<=n1,n2<g.nbN) */
Arete getAreteNoeuds(const Graphe* g, int n1, int n2);

/* Définit a comme l'Arete de g qui relie les sommets d'indices
   n1 et n2 (0<=n1,n2<g.nbN) */
void setAreteNoeuds(Graphe* g, int n1, int n2, const Arete a);

/* Définit posX et posY comme les coordonnées du i-ème sommet 
   de g (0<=i<g.nbN) */
void setCoordonneesINoeudGraphe(Graphe* g, const int i, const int posX, const int posY);



/* ALGORITHMES DE COMPLETION */

/* Complète le sous-graphe de g induit par ses Noeuds importants de
   telle sorte que toutes les arêtes absentes au départ aient un poids
   égal à la distance euclidienne entre les sommets qu'elles relient */
void completerEuclide(Graphe* g);

/* Retourne une Arete correspondant au plus court chemin entre les
   sommets d'indices n1 et n2 dans g (0<=n1,n2<g.nbN) */
Arete PCC(Graphe* g, const int n1, const int n2);

/* Complète le sous-graphe de g induit par ses Noeuds importants de
   telle sorte que toutes les arêtes absentes au départ soient des
   plus courts chemins entre les sommets qu'elles relient */
void completerPCC(Graphe* g);



/* ALGORITHMES DE KRUSKAL */

/* Retourne un tableau d'Aretes formant un arbre couvrant de g de poids
   minimal, et définit longsol comme la longueur de ce tableau. g doit
   avoir été complété avec completerEuclide préalablement. */
Arete* kruskal(const Graphe* g, int* longsol);

/* Retourne un tableau d'Aretes (toutes de longueur 2) formant un arbre
   couvrant de g de poids minimal, et définit longsol comme la longueur
   de ce tableau. g doit avoir été complété avec completerPCC préalablement. */
Arete* kruskal2(const Graphe* g, int* longsol);



/* FONCTIONS D'AFFICHAGE EN MODE TEXTE */

/* Affiche dans la console les différents attributs du graphe g */
void affichageGrapheTexte(const Graphe* g);

/* Affiche dans la console le tableau d'Aretes tab de longueur longueur,
   considéré comme un ensemble de routes à rénover (les Aretes de tab
   doivent être des Aretes de g) */
void affichageSolutionTexte(const Graphe* g, const Arete* tab, const int longueur);



/* FONCTION DE TEST */

/* Teste les fonctions du module Graphe
   Les affichages dans la console attestent du travail en cours
   Retourne 0 si le test est concluant */
int testGraphe();

#endif


